BZOJ 1604 奶牛的邻居

Description

了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的N(1≤N≤100000)只奶牛,你会发现她们已经结成了几个“群”.每只奶牛在吃草的时候有一个独一无二的位置坐标Xi,Yi(l≤Xi,Yi≤[1..10^9];Xi,Yi∈整数.当满足下列两个条件之一,两只奶牛i和j是属于同一个群的:
1.两只奶牛的曼哈顿距离不超过C(1≤C≤10^9),即lXi - xil+IYi - Yil≤C.
2.两只奶牛有共同的邻居.即,存在一只奶牛k,使i与k,j与k均同属一个群.
给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

Input

第1行输入N和C,之后N行每行输入一只奶牛的坐标.

Output

仅一行,先输出牛群数,再输出最大牛群里的牛数,用空格隔开.

Sample Input

4 2
1 1
3 3
2 2
10 10

Sample Output

2 3

Solution

多年前的大坑
尝试了多种乱搞都过不了
老老实实来写平衡树了……
就是先把曼哈顿距离变形
排序维护treap中元素x差值小于等于c,然后按y值放进treap,放之前求一下前驱后继,然后距离小于等于c的话并查集连一下
//学习了一下启发式,然而并没有卡

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<bits/stdc++.h>

#define maxn 100000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct treap{
int s[2];
int w,v,size;
}tr[maxn];

struct coors{
int x,y;
}coor[maxn];

int f[maxn],num[maxn];
int root,size;
int n,c,ans,cnt;

bool comp(coors a,coors b)
{

return a.x<b.x;
}

int find(int x)
{

return f[x]==x ? x : f[x]=find(f[x]);
}

void unite(int x,int y)
{

int fx=find(x),fy=find(y);
if( fx==fy ) return ;
if( num[fx]>num[fy] )
f[fy]=fx,num[fx]+=num[fy];
else
f[fx]=fy,num[fy]+=num[fx];
}

void rotate(int &x,int t)
{

int son=tr[x].s[t];
tr[x].s[t]=tr[son].s[t^1];
tr[son].s[t^1]=x,x=son;
}

void del(int &x,int k)
{

int t=0;
if( tr[x].w==k ){
int l=tr[x].s[0],r=tr[x].s[1];
if( l+r ){
if( tr[l].v<tr[r].v ) t=1;
rotate(x,t),del(tr[x].s[t^1],k);
}
else x=0;
return ;
}
if( k>tr[x].w ) t=1;
del(tr[x].s[t],k);
}

void insert(int &x,int k)
{

int t=0;
if( x==0 ){
x=++size;
tr[x].w=k,tr[x].v=rand();
return ;
}
if( k>tr[x].w ) t=1;
insert(tr[x].s[t],k);
if( tr[size].v>tr[x].v ) rotate(x,t);
}

void Pre(int x,int k,int &t)
{

if( x==0 ) return ;
int l=tr[x].s[0],r=tr[x].s[1];
if( k>=tr[x].w ){
if( t==0 || tr[x].w>tr[t].w ) t=x;
Pre(r,k,t);
}
else if( k<tr[x].w ) Pre(l,k,t);
}

void Pos(int x,int k,int &t)
{

if( x==0 ) return ;
int l=tr[x].s[0],r=tr[x].s[1];
if( k<=tr[x].w ){
if( t==0 || tr[x].w<tr[t].w ) t=x;
Pos(l,k,t);
}
else if( k>tr[x].w ) Pos(r,k,t);
}

void solve()
{

sort(coor+1,coor+n+1,comp);
for(int i=1;i<=n;i++) f[i]=i,num[i]=1;
int ord=1;
for(int i=1;i<=n;i++){
while( coor[ord].x<coor[i].x-c ){
del(root,coor[ord].y);
ord++;
}
int pre=0,pos=0;
Pre(root,coor[i].y,pre),Pos(root,coor[i].y,pos);
if( pre!=0 && abs(coor[pre].y-coor[i].y)<=c ) unite(pre,i);
if( pos!=0 && abs(coor[pos].y-coor[i].y)<=c ) unite(pos,i);
insert(root,coor[i].y);
}
for(int i=1;i<=n;i++)
if( i==find(i) ){
cnt++;
ans=max(ans,num[i]);
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("1604.in","r",stdin);
freopen("1604.out","w",stdout);
#endif
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
coor[i].x=x+y,coor[i].y=x-y;
}
solve();
printf("%d %d",cnt,ans);
return 0;
}